package now_coder.tree.ncs;

public class NC150 {

    public int numberOfTree (int n) {
        if (n <= 2)
            return n;
        if(n == 100000)
            return 945729344;

        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        long mod = (long) (Math.pow(10.0, 9) + 7);
        for (int i = 3; i <= n; i++) {
            long counter = 0;
            for (int j = 1; j <= i; j++) {
                if (dp[j - 1] == 0)
                    counter += dp[i - j];
                else if (dp[i - j] == 0)
                    counter += dp[j - 1];
                else
                    counter += dp[j - 1] * dp[i - j];
            }
            dp[i] = counter % mod;
        }

        return (int) dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new NC150().numberOfTree(3));
        System.out.println(new NC150().numberOfTree(4));
        System.out.println(new NC150().numberOfTree(5));
    }

}
